/// 哈希表容量候选素数序列
/// 用于动态扩容时选择最接近需求容量的素数
pub const SET_PRIMES: &[usize] = &[
    193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869, 3145739, 6291469,
    12582917, 25165843, 50331653, 100663319, 201326611,
    402653189, 805306457, 1610612741
];

/// 泛型哈希函数类型
pub type SetHashFunc<T> = fn(&T) -> u64;

/// 泛型相等比较函数类型
pub type SetEqualFunc<T> = fn(&T, &T) -> bool;

/// 泛型值释放函数类型
pub type SetFreeFunc<T> = Box<dyn Fn(T) + 'static>;

/// 哈希表中的条目节点，包含数据值和下一个节点的指针
#[derive(Debug)]
pub struct SetEntry<T> {
    pub data: T,
    pub next: Option<Box<SetEntry<T>>>,
}


/// 泛型集合容器结构体
/// 使用链地址法解决哈希冲突，包含哈希表元数据和操作函数
pub struct Set<T> {
    /// 哈希桶数组，每个元素是链表的头节点
    table: Vec<Option<Box<SetEntry<T>>>>,
    /// 当前集合中的元素数量
    entries: usize,
    /// 哈希表当前容量（桶的数量）
    table_size: usize,
    /// 当前使用的素数索引（指向SET_PRIMES数组）
    prime_index: usize,
    /// 元素哈希值计算函数
    hash_func: SetHashFunc<T>,
    /// 元素相等性判断函数
    equal_func: SetEqualFunc<T>,
    /// 元素释放回调函数
    free_func: SetFreeFunc<T>,
}


impl<T> Set<T> {
    /// 获取集合中元素的数量
    pub fn num_entries(&self) -> usize {
        self.entries
    }

    /// 注册元素释放回调函数
    /// 注册元素释放回调函数
    pub fn register_free_function<F: 'static + Fn(T)>(&mut self, free_func: F) {
        self.free_func = Box::new(free_func);
    }

    /// 查询集合中是否存在指定元素
    ///
    /// 使用哈希函数计算元素哈希值后，通过取模运算确定哈希链索引，
    /// 遍历对应哈希链中的所有节点，使用相等性判断函数进行比较。
    ///
    /// # 参数
    /// - `data`: 待查询元素的不可变引用
    ///
    /// # 返回值
    /// - `true` 表示元素存在于集合中
    /// - `false` 表示元素不存在于集合中
    pub fn query(&self, data: &T) -> bool {
        unimplemented!("set_query not yet implemented")
    }
    /// 
    /// # 参数
    /// - `data`: 待查询的元素的引用
    /// 
    /// # 返回值
    /// 如果元素存在于集合中返回true，否则返回false
    pub fn contains(&self, data: &T) -> bool {
        // 计算哈希索引
        let hash_value = (self.hash_func)(data);
        let index = (hash_value as usize) % self.table.len();

        // 遍历哈希链
        let mut current = self.table[index].as_deref();
        while let Some(entry) = current {
            if (self.equal_func)(data, &entry.data) {
                return true;
            }
            current = entry.next.as_deref();
        }

        false
    }

    /// 分配哈希表内存并初始化
    /// 
    /// 根据当前素数索引或元素数量计算表大小，分配对应容量的Vec<Option<Box>>结构
    /// 保留原始防御性编程逻辑，处理极端情况下表容量为0的无效状态
    /// 
    /// # 返回值
    /// 成功分配返回true，无效容量返回false
    /// 分配哈希表内存并初始化
    /// 
    /// 根据当前素数索引或元素数量计算表大小，分配对应容量的Vec<Option<Box>>结构
    /// 保留原始防御性编程逻辑，处理极端情况下表容量为0的无效状态
    /// 
    /// # 返回值
    /// 成功分配返回true，无效容量返回false
    fn allocate_table(&mut self) -> bool {
        let table_size = match self.prime_index < SET_PRIMES.len() {
            true => SET_PRIMES[self.prime_index],
            false => self.entries.saturating_mul(10)
        };

        if table_size == 0 {
            return false;
        }

        self.table = (0..table_size).map(|_| None).collect();
        self.table_size = table_size;
        true
    }

    /// 安全释放集合条目及其关联数据
    ///
    /// 如果注册了释放函数，将先调用该函数处理数据域。
    /// 条目内存通过所有权转移自动回收，无需显式释放。
    ///
    /// # 参数
    fn free_entry(free_func: &SetFreeFunc<T>, entry: Box<SetEntry<T>>) {
        let data = entry.data;
        (free_func)(data);
    }

    /// 创建集合的迭代器并初始化遍历状态
    ///
    /// 返回初始化完成的集合迭代器实例
    pub fn iterate(&self) -> SetIter<T> {
        SetIter::new(self)
    }

    pub fn iter(&self) -> SetIter<T> {
        SetIter::new(self)
    }
}

/// 集合迭代器结构体
pub struct SetIter<'a, T> {
    set: &'a Set<T>,
    current_bucket: usize,
    current_entry: Option<&'a SetEntry<T>>,
}

impl<'a, T> SetIter<'a, T> {
    /// 初始化集合迭代器，定位到第一个有效元素。
    ///
    /// 遍历哈希表的所有桶，找到第一个非空桶，将迭代器的`current_entry`指向该桶的首个条目，
    /// 并设置`current_bucket`为当前桶索引，以支持后续遍历。
    ///
    /// # 参数
    /// - `set`: 要遍历的集合的不可变引用
    ///
    /// # 返回值
    /// 返回初始化后的集合迭代器实例
    pub fn new(set: &'a Set<T>) -> Self {
        let mut current_bucket = 0;
        let mut current_entry = None;

        // 线性探测寻找第一个非空哈希链
        while current_bucket < set.table.len() {
            if let Some(entry) = set.table[current_bucket].as_deref() {
                current_entry = Some(entry);
                break;
            }
            current_bucket += 1;
        }

        SetIter {
            set,
            current_bucket,
            current_entry,
        }
    }
}

impl<'a, T> Iterator for SetIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        // 处理当前链表节点
        if let Some(entry) = self.current_entry.take() {
            let result = &entry.data;
            self.current_entry = entry.next.as_deref();
            return Some(result);
        }

        // 移动到下一个桶并寻找非空链表
        while self.current_bucket < self.set.table.len() {
            self.current_bucket += 1;
            if self.current_bucket >= self.set.table.len() {
                break;
            }
            if let Some(entry) = self.set.table[self.current_bucket].as_deref() {
                self.current_entry = entry.next.as_deref();
                return Some(&entry.data);
            }
        }

        None
    }
}

impl<T> Set<T> {
    /// 创建新的集合实例
    ///
    /// 初始化集合结构体各字段，调用allocate_table分配哈希表内存
    /// 返回Option包装的集合实例，分配失败时返回None
    pub fn new(
        hash_func: SetHashFunc<T>,
        equal_func: SetEqualFunc<T>,
    ) -> Option<Self> {
        let mut new_set = Self {
            prime_index: 0,
            hash_func,
            equal_func,
            free_func: Box::new(|_| {}),
            table_size: 0,
            entries: 0,
            table: Vec::new(),
        };

        if new_set.allocate_table() {
            Some(new_set)
        } else {
            None
        }
    }

    /// 从集合中移除指定元素
    ///
    /// 通过哈希函数定位元素所在哈希链，遍历链表查找匹配元素。若找到则执行以下操作：
    /// 1. 从链表中摘除该节点
    /// 2. 更新元素计数器
    /// 3. 调用释放函数销毁元素数据
    ///
    /// # 参数
    /// - `data`: 要删除的元素的引用
    ///
    /// # 返回值
    /// - `true` 表示元素存在且已成功删除
    /// - `false` 表示元素不存在于集合中
    pub fn remove(&mut self, data: &T) -> bool {
        // 计算哈希索引
        let hash_value = (self.hash_func)(data);
        let index = (hash_value as usize) % self.table.len();

        // 获取当前哈希链的可变引用
        let mut current = &mut self.table[index];
        
        // 遍历哈希链查找目标元素
        while let Some(mut entry) = current.take() {
            if (self.equal_func)(data, &entry.data) {
                // 找到匹配元素，重新连接链表
                *current = entry.next.take();
                self.entries -= 1;
                
                // 释放数据
                Self::free_entry(&self.free_func, entry);
                return true;
            }
            // 恢复当前指针并移动到下一个节点
            *current = Some(entry);
            current = &mut current.as_mut().unwrap().next;
        }

        false
    }
    ///
    /// 使用哈希函数定位存储位置，采用链地址法解决冲突。
    /// 当元素已存在时返回false，插入成功返回true。
    ///
    /// # 参数
    /// - `data`: 要插入的元素值
    ///
    /// # 返回值
    /// - `true` 表示插入成功
    /// - `false` 表示元素已存在或内存分配失败
    /// 向集合中插入新元素
    ///
    /// 使用哈希函数定位存储位置，采用链地址法解决冲突。
    /// 当元素已存在时返回false，插入成功返回true。
    ///
    /// # 参数
    /// - `data`: 要插入的元素值
    ///
    /// # 返回值
    /// - `true` 表示插入成功
    /// - `false` 表示元素已存在或内存分配失败
    pub fn insert(&mut self, data: T) -> bool {
        let hash_value = (self.hash_func)(&data);
        let index = (hash_value as usize) % self.table_size;
    
        // 检查元素是否已存在
        if self.contains(&data) {
            return false;
        }
    
        // 创建新节点并插入链表头部
        let new_entry = Box::new(SetEntry {
            data,
            next: self.table[index].take(),
        });
    
        self.table[index] = Some(new_entry);
        self.entries += 1;
    
        // 此处应添加自动扩容逻辑（需配合实现enlarge方法）
        true
    }
}

impl<T> Set<T> {
    /// 计算两个集合的并集，返回新的集合
    ///
    /// 新集合包含两个输入集合中的所有唯一元素。使用第一个集合的哈希函数和相等比较函数。
    /// 在插入过程中会自动处理内存分配失败的情况。
    ///
    /// # 参数
    /// - `set1`: 第一个集合的引用
    /// - `set2`: 第二个集合的引用
    ///
    /// # 返回值
    /// - `Some(Set<T>)` 表示成功创建的并集集合
    /// - `None` 表示内存分配失败或插入操作失败
    pub fn union(set1: &Set<T>, set2: &Set<T>) -> Option<Self>
    where
        T: Clone,
    {
        let mut new_set = Set::new(set1.hash_func, set1.equal_func)?;

        // 插入第一个集合的所有元素
        for item in set1.iter() {
            if !new_set.insert(item.clone()) {
                return None;
            }
        }

        // 插入第二个集合的未重复元素
        for item in set2.iter() {
            if !new_set.contains(item) {
                if !new_set.insert(item.clone()) {
                    return None;
                }
            }
        }

        Some(new_set)
    }
    pub fn to_array(&self) -> Vec<&T> {
        self.iter().collect()
    }
}

impl<T> Set<T> {
    /// 计算两个集合的交集并返回新集合
    ///
    /// 使用第一个集合的哈希函数和第二个集合的相等比较函数创建新集合。
    /// 遍历第一个集合的所有元素，当元素同时存在于第二个集合时插入新集合。
    ///
    /// # 参数
    /// - `set1`: 第一个集合的引用
    /// - `set2`: 第二个集合的引用
    ///
    /// # 返回值
    /// - `Some(Set<T>)`: 成功时包含交集的新集合
    /// - `None`: 内存分配失败或插入失败时返回
    pub fn intersection(set1: &Set<T>, set2: &Set<T>) -> Option<Self>
    where
        T: Clone,
    {
        let mut new_set = Self::new(set1.hash_func, set2.equal_func)?;

        for value in set1.iter() {
            if set2.contains(value) {
                if !new_set.insert(value.clone()) {
                    return None;
                }
            }
        }

        Some(new_set)
    }
}
impl<T: std::fmt::Debug> std::fmt::Debug for Set<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Set")
            .field("table", &self.table)
            .field("entries", &self.entries)
            .field("table_size", &self.table_size)
            .field("prime_index", &self.prime_index)
            .field("hash_func", &self.hash_func)
            .field("equal_func", &self.equal_func)
            .finish_non_exhaustive()
    }
}
impl<T> Drop for Set<T> {
    fn drop(&mut self) {
        for bucket in &mut self.table {
            let mut current = bucket.take();
            while let Some(mut entry) = current {
                current = entry.next.take();
                Self::free_entry(&self.free_func, entry);
            }
        }
    }
}